package com.ztom.top100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 根据身高重建队列
 * <p>
 * https://leetcode-cn.com/problems/queue-reconstruction-by-height/
 *
 * @author ZhangTao
 */
public class Code86ReconstructQueue {

    public int[][] reconstructQueue(int[][] people) {
        if (people == null || people.length == 0 || people[0].length == 0) {
            return new int[0][0];
        }
        List<int[]> res = new ArrayList<>();
        // 先排队: 按身高降序, k 升序
        Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
        // 再插队: 根据 k 值直接插队
        for (int[] person : people) {
            res.add(person[1], person);
        }

        return res.toArray(new int[res.size()][2]);
    }
}
